// 1011. 在 D 天内送达包裹的能力
// https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/description/?orderBy=most_votes
// 中等,传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
// 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出
// 重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
// 返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。
// 输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
// 输出：15
// 输入：weights = [3,2,2,4,1,4], days = 3
// 输出：6
// 输入：weights = [1,2,3,1,1], days = 4
// 输出：3

#include <bits/stdc++.h>
using namespace std;

class Solution {
  bool Check(vector<int>& ws, size_t load, int days) {
    int ship = 0;
    for (size_t i = 0; i < ws.size(); ship++) {
      int carry = 0; // 运送/船次
      while (i<ws.size() && carry+ws[i]<=load)  {
        carry += ws[i++];
      }
    }
    return ship <= days;
  }
public:
  int shipWithinDays(vector<int>& ws, int days) {
    int maxW = 0;
    int sum = 0;
    for(auto w : ws) {
      maxW = max(maxW, w);
      sum += w;
    }
    int l = maxW;
    int r = sum;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (Check(ws, mid, days)) {
        r = mid;  // [mid, sum]
      } else {
        l = mid + 1; // [maxW, mid+1]
      }
    }
    return r; // or l
  }
};
